package offer

import (
	"math/rand"
	"sort"
)

/*
时间复杂度:O(N) 计算前缀和所需要的时间
空间复杂度:O(N) 存储前缀和数组所需要的空间
*/

type Solution struct {
	pre []int
	n   int
}

func Constructor(w []int) Solution {
	for i := 1; i < len(w); i++ {
		w[i] += w[i-1]
	}
	n := w[len(w)-1]
	return Solution{
		pre: w,
		n:   n,
	}
}

func (this *Solution) PickIndex() int {
	// rand.Intn(M)生成[0, M)范围的整数
	// rand.Intn(M)+1 生成 [1, M]范围的整数
	num := rand.Intn(this.n) + 1
	ans := sort.SearchInts(this.pre, num)
	return ans
}

/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(w);
 * param_1 := obj.PickIndex();
 */
